package 力扣.回溯;

import sun.security.x509.AttributeNameEnumeration;

import java.util.ArrayList;
import java.util.List;

public class 电话号码的字母组合17 {
    public List<String> letterCombinations(String digits) {
         if (digits == null || digits.length() == 0){
             return new ArrayList<>();
         }
         StringBuffer box = new StringBuffer();
         int i = 0;//从第0个人开始
         List<String> ans = new ArrayList<>();
         backTrace(digits,i,ans,box);
         return ans;
    }
    final String[] ds = new String[] { //
            "", // 0
            "", // 1
            "abc", // 2
            "def", // 3
            "ghi", // 4
            "jkl", // 5
            "mno", // 6
            "pqrs", // 7
            "tuv", // 8
            "wxyz" // 9
    };
    private void backTrace(String digits, int i, List<String> ans, StringBuffer box) {
         int N = digits == null ? 0 : digits.length();
         if (box.length() == N){//查看箱子状态，并判断满足条件是啥
             ans.add(box.toString());
         }
         if (i >= N){//什么时候越界
             return;
         }
         //遍历第i个人拿宝石（宝石的选项是啥）
         int stoneIndex = (int)(digits.charAt(i) - '0');
        for (int j = 0; j < ds[stoneIndex].length(); j++) {
            char c = ds[stoneIndex].charAt(j);//拿到宝石
            box.append(c);//放入箱子中
            backTrace(digits, i + 1, ans, box);//处理下一个人
            box.deleteCharAt(box.length() - 1);//取出自己的宝石，将箱子恢复原样
        }

    }

    public List<String> letterCombinations2(String digits) {
          if (digits == null || digits.length() == 0){
              return new ArrayList<>();
          }
          List<String> ans = new ArrayList<>();
          StringBuffer box = new StringBuffer();
          backTrace2(digits,0,ans,box);
          return ans;
    }

    private void backTrace2(String digits, int i, List<String> ans, StringBuffer box) {
        if (i == digits.length()){
            ans.add(box.toString());
        }
        if (i >= digits.length()){
            return;
        }
        int nums = digits.charAt(i) - '0';
        String s = ds[nums];
        for (int j = 0; j < s.length(); j++) {
            char c = s.charAt(j);
            box.append(c);
            backTrace2(digits, i+1, ans, box);
            box.deleteCharAt(box.length() - 1);
        }
    }
}
